// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 * Creator: yanking
 * Create time: 2022-02-26 16:55
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.GraphyTrain;

import java.util.*;

public class IsSymmetricTreeIterator {
    // 使用迭代方法
    // 通过引入队列实现迭代方法，左右子树进入队列的顺序应该不一样


    public boolean isSymmetric(TreeNode root) {

        return check(root, root);
    }

    private boolean check(TreeNode u, TreeNode v) {
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(u);
        q.offer(v);
        while (!q.isEmpty()) {
            u = q.poll();
            v = q.poll();

            if (u == null && v == null) {
                continue;
            }
            if (u == null || v == null || u.val != v.val) {
                return false;
            }
            // 保证连续连个相同的值在一起
            q.offer(u.left);
            q.offer(v.right);
            q.offer(u.right);
            q.offer(v.left);

        }
        return true;

    }


    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
